package com.freedy.dataStructure.search;

import com.freedy.dataStructure.sort.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Freedy
 * @date 2021/3/22 21:53
 */
public class InsertSearch {
    public static int count = 0;

    public static void main(String[] args) {
        Test.MAX_TEST_DATA = 100000;
        int[] ints = Test.randomArrMaker();
        ints[50] = 5345343;
        Arrays.sort(ints);
        System.out.println(Arrays.toString(mulSearch(ints, 0, ints.length - 1, 5345343)));
        System.out.println(count);
    }

    /**
     * 是上面方法的加强,可以找到多个索引
     */
    public static int[] mulSearch(int[] arr, int left, int right, int findVal) {
        count++;
        if (findVal<arr[left]||findVal>arr[right]) return new int[]{-1};
        int mid = left == right ? left : (int)((double)left + (double)(findVal - arr[left]) / (double)(arr[right] - arr[left]) * (double)(right - left));
        int midVal = arr[mid];
        if (findVal > midVal) {
            if (left == right) return new int[]{-1};
            return mulSearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            if (left == right) return new int[]{-1};
            return mulSearch(arr, left, mid-1, findVal);
        } else {
            int lIndex = mid;
            int rIndex = mid + 1;
            List<Integer> list = new ArrayList<>();
            while (lIndex >= left && arr[lIndex] == findVal) {
                list.add(lIndex);
                lIndex--;
            }
            while (rIndex <= right && arr[rIndex] == findVal) {
                list.add(rIndex);
                rIndex++;
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }
}
